package org.basis.algorithm.list;

import org.basis.algorithm.list.common.SingleNode;

import java.util.HashSet;

/**
 * 无环链表相交问题
 * 两个无环链表相交，如果相交则找出他们的相交节点
 *
 * @author Mr_wenpan@163.com 2021/12/15 11:49
 */
public class AcyclicListsIntersect {

    public static void main(String[] args) {

    }

    /**
     * 使用hash表来求解两个无环单链表相交问题
     */
    public static SingleNode<Integer> findNodeByHash(SingleNode<Integer> head1, SingleNode<Integer> head2) {
        if (head1 == null || head2 == null) {
            return null;
        }

        HashSet<SingleNode<Integer>> set = new HashSet<>();
        while (head1 != null) {
            set.add(head1);
            head1 = head1.next;
        }

        while (head2 != null) {
            if (set.contains(head2)) {
                return head2;
            }
            head2 = head2.next;
        }

        return null;
    }

    /**
     * 使用快慢指针来求解两个无环单链表相交问题
     */
    public static SingleNode<Integer> findNodeByPoint(SingleNode<Integer> head1, SingleNode<Integer> head2) {

        if (head1 == null || head2 == null) {
            return null;
        }

        // 统计两个链表的长度差值
        int len = 0;
        SingleNode<Integer> cur1 = head1;
        SingleNode<Integer> cur2 = head2;
        while (cur1 != null) {
            len++;
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            len--;
            cur2 = cur2.next;
        }

        // 长链表短链表
        SingleNode<Integer> longList = len > 0 ? head1 : head2;
        SingleNode<Integer> shortList = longList == head1 ? head2 : head1;

        // 长链表先走差值步
        for (int i = 0; i < Math.abs(len); i++) {
            longList = longList.next;
        }

        // 长短链表一起走
        while (longList != null && shortList != null) {
            if (longList == shortList) {
                return longList;
            }
            longList = longList.next;
            shortList = shortList.next;
        }

        return null;
    }

    /**
     * 有环链表相交，找到相交节点（明确知道两个链表都有环的情况）
     */
    public static SingleNode<Integer> findNodeByPoint2(SingleNode<Integer> head1, SingleNode<Integer> head2) {
        if (head1 == null || head2 == null) {
            return null;
        }

        SingleNode<Integer> ringNode1 = null;
        SingleNode<Integer> ringNode2 = null;
        // 先找到两个链表的入环节点
        SingleNode<Integer> fast = head1;
        SingleNode<Integer> slow = head1;
        boolean hasLoop = false;

        while (fast != null) {
            slow = slow.next;
            fast = fast.next == null ? null : fast.next.next;
            if (fast == slow) {
                hasLoop = true;
                break;
            }
        }
        if (hasLoop) {
            fast = head1;
            while (fast != null && fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
            ringNode1 = fast;
        }

        hasLoop = false;
        fast = head2;
        slow = head2;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next == null ? null : fast.next.next;
            if (fast == slow) {
                hasLoop = true;
                break;
            }
        }
        if (hasLoop) {
            fast = head2;
            while (fast != null && fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
            ringNode2 = fast;
        }

        // 任意一个链表的入环节点为空都说明没有相交（题目说了两个有环链表）
        if (ringNode1 == null || ringNode2 == null) {
            return null;
        }

        // 看看两个链表入环节点是否是同一个
        // 如果是，则从两个链表的头节点到入环节点处，按照单链表相交方式来处理
        if (ringNode1 == ringNode2) {
            int len = 0;
            SingleNode<Integer> cur1 = head1;
            SingleNode<Integer> cur2 = head2;
            // 求两个链表从头节点到入环节点的节点个数差值
            while (cur1 != ringNode1) {
                len++;
                cur1 = cur1.next;
            }
            while (cur2 != ringNode2) {
                len--;
                cur2 = cur2.next;
            }
            SingleNode<Integer> longList = len > 0 ? head1 : head2;
            SingleNode<Integer> shortList = longList == head1 ? head2 : head1;

            // 两个链表一样长，且有一个共同入环节点，那么说明这两个节点的入环节点就是他们第一次相交的节点
            if (len == 0) {
                return ringNode1;
            }

            // 长链表先走差值步
            for (int i = 0; i < Math.abs(len); i++) {
                longList = longList.next;
            }
            // 长短链表一起走
            while (longList != ringNode1 && shortList != ringNode1) {
                // 一旦相遇，则相遇的节点就是
                if (longList == shortList) {
                    return longList;
                }
                longList = longList.next;
                shortList = shortList.next;
            }
            // 否则，他们就在入环节点第一次相交
            return longList;
        } else {
            // 如果不是，则任意找一个入环节点，从该节点开始沿着环走一圈，如果能遇到另外一个节点，则说明相交，任意返回一个入环节点即可，反之则不相交
            SingleNode<Integer> cur = ringNode1.next;
            while (cur != ringNode1) {
                if (cur == ringNode2) {
                    return ringNode1;
                }
                cur = cur.next;
            }
            // 不相交
            return null;
        }

    }


    /**
     * 查找两个链表相交的节点（综合）：两条链表可以都有环，也可以都没有环，也可以一个有环一个没环，可以相交也可以不相交
     * 如果相交，总的来说分为三种情况：
     * 1、两个链表都无环情况
     * 2、两个链表都有环，但入环节点各不相同情况
     * 3、两个链表都有环，入环节点各相同情况
     * 链表相交有且只有上述三种情况，根据上面分析可以看出可以分为有环和无环来判断
     */
    public static SingleNode<Integer> findNode(SingleNode<Integer> head1, SingleNode<Integer> head2) {
        if (head1 == null || head2 == null) {
            return null;
        }

        // 查找两个链表的入环节点
        SingleNode<Integer> ringNode1 = findRingNode(head1);
        SingleNode<Integer> ringNode2 = findRingNode(head2);

        // 都没有环的情况，使用快慢指针来做
        if (ringNode1 == null && ringNode2 == null) {
            SingleNode<Integer> cur = head1;
            int len = 0;
            // 求两个链表的差值
            while (cur != null) {
                cur = cur.next;
                len++;
            }
            cur = head2;
            while (cur != null) {
                cur = cur.next;
                len--;
            }

            SingleNode<Integer> longList = len > 0 ? head1 : head2;
            SingleNode<Integer> shortList = longList == head1 ? head2 : head1;

            // 长链表先走差值步
            for (int i = 0; i < Math.abs(len); i++) {
                longList = longList.next;
            }

            // 长短链表一起走
            while (longList != null && shortList != null) {
                longList = longList.next;
                shortList = shortList.next;
                if (longList == shortList) {
                    return longList;
                }
            }
            // 不相交
            return null;
        }

        // 一个有环一个没环一定不相交
        if (ringNode1 == null || ringNode2 == null) {
            return null;
        }

        // 都有环的情况
        return findNode(head1, ringNode1, head2, ringNode2);
    }

    public static SingleNode<Integer> findNode(SingleNode<Integer> head1,
                                               SingleNode<Integer> ringNode1,
                                               SingleNode<Integer> head2,
                                               SingleNode<Integer> ringNode2) {

        if (head1 == head2) {
            return head1;
        }
        SingleNode<Integer> cur1 = head1;
        SingleNode<Integer> cur2 = head2;
        // 入环节点是同一个，那么他们一定相交，找出他们第一个相交的节点
        if (ringNode1 == ringNode2) {
            // 两个链表从头开始走，走到入环节点为止，统计长度
            int len = 0;
            while (cur1 != ringNode1) {
                cur1 = cur1.next;
                len++;
            }
            while (cur2 != ringNode1) {
                cur2 = cur2.next;
                len--;
            }

            SingleNode<Integer> longList = len > 0 ? head1 : head2;
            SingleNode<Integer> shortList = longList == head1 ? head2 : head1;

            // 长链表先走差值步
            for (int i = 0; i < Math.abs(len); i++) {
                longList = longList.next;
            }

            // 长短链表一起走，第一个相等的节点就是他们第一个相交的节点
            while (longList != null && shortList != null) {
                if (longList == shortList) {
                    return longList;
                }
                longList = longList.next;
                shortList = shortList.next;
            }
            // 不相交，不可能走到这里
            return null;
        } else {
            // 从一个入环节点开始，绕环走一圈，如果能遇到第二个入环节点，那么就相交，返回任意一个入环节点即可
            SingleNode<Integer> cur = ringNode1.next;
            while (cur != ringNode1) {
                if (cur == ringNode2) {
                    return ringNode2;
                }
                cur = cur.next;
            }
            // 不相交
            return null;
        }

    }

    /**
     * 查找链表的入环节点
     */
    public static SingleNode<Integer> findRingNode(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return null;
        }
        SingleNode<Integer> fast = head;
        SingleNode<Integer> slow = head;
        boolean hasLoop = false;
        while (fast != null) {
            fast = fast.next == null ? null : fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                hasLoop = true;
                break;
            }
        }

        if (hasLoop) {
            fast = head;
            // 快慢指针同时走，相交的点就是入环节点
            while (fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
        return null;
    }

}
